home *** CD-ROM | disk | FTP | other *** search
/ PsL Monthly 1993 December / PSL Monthly Shareware CD-ROM (December 1993).iso / prgmming / dos / pascal / miscuni.com / QUEUES.PAS < prev    next >
Encoding:
Pascal/Delphi Source File  |  1989-05-25  |  5.6 KB  |  167 lines
  1. {.he Queue Maintenance Routines - %F}
  2. (********************************************************************)
  3. (*                             Queues                               *)
  4. (*                                                                  *)
  5. (*  Author: Geoff Moehrke                                           *)
  6. (*  Date: August 27, 1988                                           *)
  7. (*                                                                  *)
  8. (*  Purpose: Queue implementation, allows queueing of any data type *)
  9. (*           using Turbo Pascal's generic pointers to reference     *)
  10. (*           queued data.                                           *)
  11. (*                                                                  *)
  12. (*  Source: F:\TP\UNIT\QUEUES.PAS                                   *)
  13. (********************************************************************)
  14. Unit Queues;
  15.  
  16. interface
  17.  
  18. type
  19.   QueuePtr = ^QueueRec;
  20.   QueueRec = record
  21.                Data: Pointer;   { Generic pointer to data  }
  22.                Next: QueuePtr;  { Pointer to next QueueRec }
  23.              end;
  24.  
  25.   Queue = record
  26.              DataSize : Word;   { Size of data in this queue          }
  27.              StartQ,            { Pointer to beginning of queue       }
  28.              EndQ : QueuePtr;   { Pointer to end of queue             }
  29.              Length,            { Current length of queue             }
  30.              MaxLen : Word;     { Maximum length queue reached so far }
  31.            end;
  32.  
  33.  procedure InitQ ( Var Q: Queue; Size: Word );
  34.    {- Initialize queue variables and set up for processing.          }
  35.    {  Must be called for each queue before performing any operations }
  36.    {  on it.                                                         }
  37.    {  Example: InitQ ( MyQueue, SizeOf(MyType) );                    }
  38.  
  39.  
  40.  function Enqueue(Var Q:Queue; Item: Pointer): boolean;
  41.    {- Add an item at end of queue, return True if successful.        }
  42.    {  Parameters:  Q - queue variable                                }
  43.    {               Item - generic pointer to item.  easiest way is   }
  44.    {                      to use address operator (@AnyVar)          }
  45.    {                                                                 }
  46.    {  Example: Enqueue( MyQueue, @MyVar);                            }
  47.  
  48.  function Dequeue(Var Q: Queue):Pointer;
  49.    {- Returns a pointer to the first item in the queue, nil if       }
  50.    {  queue is empty.                                                }
  51.    {                                                                 }
  52.    {  Easiest way to access data after dequeueing is to use          }
  53.    {  typecasting to the queued data type after checking for an      }
  54.    {  empty queue.  Example:                                         }
  55.    {                                                                 }
  56.    {            If Not QEmpty(MyQueue) then                          }
  57.    {               IntVar := Integer( Dequeue(MyQueue)^ );           }
  58.    {                                                                 }
  59.  
  60.  
  61.  function QEmpty(Q: Queue):Boolean;
  62.    {- determine whether queue is empty or not }
  63.  
  64.  function QSize(Q: Queue):Word;
  65.    {- returns current size (length) of queue }
  66.  
  67.  function MaxQSize(Q: Queue):Word;
  68.    {- ruturns the maximum size (length) that Q has reached  }
  69.  
  70. implementation
  71.  
  72.  procedure InitQ(Var Q: Queue; Size: Word);
  73.    {- Initialize queue variables and set up for processing }
  74.  
  75.    begin
  76.      with Q do begin
  77.        StartQ := nil;
  78.        EndQ := nil;
  79.        DataSize := Size;
  80.        Length := 0;
  81.        MaxLen := 0;
  82.      end;
  83.    end;
  84.  
  85.  {$F+}
  86.  function HeapFunc( Size : Word ): Integer;
  87.    {- Prevent New() or GetMem() from causing a run-time error if
  88.       memory not available (See TP manual - Chapter 15).         }
  89.  
  90.    begin
  91.      HeapFunc := 1;
  92.    end;
  93.  {$F-}
  94.  
  95.  
  96.  function Enqueue(Var Q:Queue; Item: Pointer): Boolean;
  97.    {- Add an item at end of queue return true if successful }
  98.  
  99.    var NewItem, Temp:QueuePtr;
  100.  
  101.    begin
  102.      Enqueue := False;
  103.      New(NewItem);
  104.      if NewItem = nil then
  105.        Exit;                { Insufficient memory  }
  106.      GetMem(NewItem^.Data,Q.DataSize);
  107.      if NewItem^.Data = nil then
  108.        Exit;
  109.      Move(Item^,NewItem^.Data^,Q.DataSize);
  110.      Temp := Q.EndQ;
  111.      Q.EndQ := NewItem;         { add new item at end }
  112.      with Q do begin
  113.        if Length = 0 then
  114.          StartQ := NewItem;
  115.        if Temp <> nil then
  116.          Temp^.Next := EndQ;
  117.        EndQ^.Next := nil;
  118.        inc(Length);             { increment the length }
  119.        if Length > MaxLen then  { adjust max length }
  120.          MaxLen := Length;
  121.        Enqueue := True;
  122.      end
  123.    end;
  124.  
  125.  function Dequeue(Var Q: Queue):Pointer;
  126.    {- Returns a pointer to the first item in the queue, nil if queue is empty }
  127.  
  128.    var Temp : QueuePtr;
  129.  
  130.    begin
  131.      Dequeue := nil;
  132.      if Q.Length = 0 then  { queue is empty - exit w/nil pointer }
  133.        exit;
  134.      with Q do begin
  135.        Dec(Length);
  136.        Dequeue := StartQ^.Data;
  137.        FreeMem(StartQ^.Data,Q.DataSize);
  138.        Temp := StartQ;
  139.        StartQ := StartQ^.Next;
  140.        If Length = 0 then
  141.          EndQ := nil;
  142.      end;
  143.    end;
  144.  
  145.  function QEmpty(Q: Queue):Boolean;
  146.    {- determine whether queue is empty or not }
  147.  
  148.    begin
  149.      QEmpty := Q.Length=0;
  150.    end;
  151.  
  152.  function QSize(Q: Queue):Word;
  153.    {- returns current size of queue }
  154.  
  155.    begin
  156.      QSize := Q.Length;
  157.    end;
  158.  
  159.  function MaxQSize(Q: Queue):Word;
  160.    {- returns maximum length Q has reached }
  161.  
  162.    begin
  163.      MaxQSize := Q.MaxLen;
  164.    end;
  165.  
  166.  
  167. end. { Unit Queues }